{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Russian Doll Envelopes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #dynamic-programming #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #动态规划 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxEnvelopes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #俄罗斯套娃信封问题"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个二维整数数组 <code>envelopes</code> ，其中 <code>envelopes[i] = [w<sub>i</sub>, h<sub>i</sub>]</code> ，表示第 <code>i</code> 个信封的宽度和高度。</p>\n",
    "\n",
    "<p>当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。</p>\n",
    "\n",
    "<p>请计算 <strong>最多能有多少个</strong> 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。</p>\n",
    "\n",
    "<p><strong>注意</strong>：不允许旋转信封。</p>\n",
    "&nbsp;\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>envelopes = [[5,4],[6,4],[6,7],[2,3]]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>最多信封的个数为 <code>3, 组合为: </code>[2,3] =&gt; [5,4] =&gt; [6,7]。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>envelopes = [[1,1],[1,1],[1,1]]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= envelopes.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>envelopes[i].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= w<sub>i</sub>, h<sub>i</sub> &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [russian-doll-envelopes](https://leetcode.cn/problems/russian-doll-envelopes/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [russian-doll-envelopes](https://leetcode.cn/problems/russian-doll-envelopes/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[5,4],[6,4],[6,7],[2,3]]', '[[1,1],[1,1],[1,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: list[list[int]]) -> int:\n",
    "        envelopes.sort(key=lambda x: [x[0], -x[1]])\n",
    "\n",
    "        dp = [envelopes[0][1]]\n",
    "        for i in range(1, len(envelopes)):\n",
    "            if envelopes[i][1] > dp[-1]:\n",
    "                dp.append(envelopes[i][1])\n",
    "            else:\n",
    "                pos = bisect.bisect_left(dp, envelopes[i][1])\n",
    "                dp[pos] = envelopes[i][1]\n",
    "\n",
    "        return len(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, e: List[List[int]]) -> int:\n",
    "        # 首先根据x的第0个元素升序排列,相同时按第1个元素降序排列\n",
    "        e.sort(key = lambda x: (x[0], -x[1]))\n",
    "        n = len(e)\n",
    "        f = [0] * n\n",
    "        for i in range(n):\n",
    "            f[i] = e[i][1]\n",
    "        ans = []\n",
    "        for x in f:\n",
    "            idx = bisect_left(ans, x)\n",
    "            if idx == len(ans):\n",
    "                ans.append(x)\n",
    "            else:\n",
    "                ans[idx] = x\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        envelopes = sorted(envelopes, key=lambda s: (s[1], -s[0]))\n",
    "        lst = [v[0] for v in envelopes]\n",
    "        return self.sub(lst)\n",
    "\n",
    "    # 最长上升子序列\n",
    "    def sub(self, lst):\n",
    "        # 扑克牌：耐心排序\n",
    "        m = len(lst)\n",
    "        top = [0] * m\n",
    "        piles = 0\n",
    "        for i in range(m):\n",
    "            poker = lst[i]\n",
    "            l, r = 0, piles\n",
    "            while l < r:\n",
    "                mid = (l + r) // 2\n",
    "                if top[mid] < poker:\n",
    "                    l = mid + 1\n",
    "                else:\n",
    "                    r = mid\n",
    "            if l == piles:\n",
    "                piles += 1\n",
    "            top[l] = poker\n",
    "        return piles\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        n = len(envelopes)\n",
    "        # 按宽度升序排列，如果宽度一样，则按高度降序排列\n",
    "        envelopes.sort(key=lambda x: (x[0], -x[1]))\n",
    "        # 对高度数组寻找 LIS\n",
    "        height = [0] * n\n",
    "        for i in range(n):\n",
    "            height[i] = envelopes[i][1]\n",
    "\n",
    "        return self.lengthOfLIS(height)\n",
    "    \n",
    "    def lengthOfLIS(self,nums):\n",
    "        n  = len(nums)\n",
    "        top = [0] * n\n",
    "        top[0] = nums[0]\n",
    "        piles = 1\n",
    "        \n",
    "        for i in range(n):\n",
    "            left = 0 \n",
    "            right = piles\n",
    "            tar = nums[i]\n",
    "            while left < right:\n",
    "                mid = left + (right - left) // 2\n",
    "                if top[mid] < tar:\n",
    "                    left = mid + 1\n",
    "                elif top[mid] > tar:\n",
    "                    right = mid\n",
    "                else:\n",
    "                    right = mid \n",
    "            if left == piles:\n",
    "                piles += 1\n",
    "\n",
    "            top[left] = tar\n",
    "\n",
    "        return piles "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        if not envelopes:\n",
    "            return 0\n",
    "        \n",
    "        n = len(envelopes)\n",
    "        envelopes.sort(key=lambda x: (x[0], -x[1]))\n",
    "\n",
    "        f = [envelopes[0][1]]\n",
    "        for i in range(1, n):\n",
    "            if envelopes[i][1] > f[-1]:\n",
    "                f.append(envelopes[i][1])\n",
    "            else:\n",
    "                index = bisect.bisect_left(f, envelopes[i][1])\n",
    "                f[index] = envelopes[i][1]\n",
    "        \n",
    "        return len(f)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        # dp[i] = max(dp[i-k] + 1) for k 满足envelope[i-k]长宽均小于envelopo[i]\n",
    "        n = len(envelopes)\n",
    "        dp = [1]*(n+1)\n",
    "        envelopes.sort(key = lambda x: (x[0],-x[1]))\n",
    "        heights = [envelope[1] for envelope in envelopes]\n",
    "        return self.lengthOfLIS(heights)\n",
    "\n",
    "    def lengthOfLIS(self, nums):\n",
    "        piles = 0\n",
    "        top = [0]*(len(nums)+1)\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            target = nums[i]\n",
    "\n",
    "            left = 0\n",
    "            right = piles\n",
    "            while left <= right:\n",
    "                mid = left + (right - left) // 2\n",
    "                if top[mid] < target:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            if left > piles:\n",
    "                piles += 1\n",
    "            top[left] = target\n",
    "        return piles\n",
    "\n",
    "\n",
    "\n",
    "        # for i in range(n):\n",
    "        #     for j in range(i):\n",
    "        #         if heights[j] < heights[i]:\n",
    "        #             dp[i] = max(dp[i], dp[j] + 1)\n",
    "        \n",
    "        # res = 1\n",
    "        # for val in dp:\n",
    "        #     res = max(res, val)\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        envelopes = sorted(envelopes, key=lambda x: (x[0], -x[1]))\n",
    "        h = [x[1] for x in envelopes]\n",
    "        dp = [1] * len(h)\n",
    "        arr = [h[0]]\n",
    "\n",
    "        for i in range(1, len(h)):\n",
    "            if h[i] > arr[-1]:\n",
    "                arr.append(h[i])\n",
    "                dp[i] = len(arr)\n",
    "\n",
    "            else:\n",
    "                l, r = 0, len(arr)-1\n",
    "                while l < r:\n",
    "                    m = (l + r) // 2\n",
    "                    if h[i] > arr[m]:\n",
    "                        l = m + 1\n",
    "                    else:\n",
    "                        r = m\n",
    "                pos = l \n",
    "                dp[i] = pos + 1\n",
    "                arr[pos] = h[i]\n",
    "        \n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self,nums):\n",
    "        n=len(nums)\n",
    "        res,tails=0,[0]*n\n",
    "        for num in nums:\n",
    "            i,j=0,res\n",
    "            while i<j:\n",
    "                m=i+(j-i)//2\n",
    "                if tails[m]<num: i=m+1\n",
    "                else: j=m\n",
    "            tails[i]=num\n",
    "            if j==res: res+=1\n",
    "        return res\n",
    "\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        envelopes.sort(key=lambda x:(x[0],-x[1]))\n",
    "        n=len(envelopes)\n",
    "        height = [0]*n\n",
    "        for i in range(n):\n",
    "            height[i]=envelopes[i][1]\n",
    "        ans = self.lengthOfLIS(height)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        # # 超时\n",
    "        # envelopes.sort(key = lambda x:(x[0],-x[1]))\n",
    "        # n = len(envelopes)\n",
    "        # dp=[1 for _ in range(n)]\n",
    "        # res = 1\n",
    "        # for i in range(1,n):\n",
    "        #     for j in range(i):\n",
    "        #         if envelopes[i][1]>envelopes[j][1]:\n",
    "        #             dp[i]=max(dp[i],dp[j]+1)\n",
    "        #     res=max(res,dp[i])   \n",
    "        # return res\n",
    "\n",
    "        def find(nums,t):\n",
    "            left=0\n",
    "            right=len(nums)-1\n",
    "            while left<=right:\n",
    "                mid=left+((right-left)>>2)\n",
    "                if nums[mid]<t:\n",
    "                    left=mid+1\n",
    "                else:\n",
    "                    right=mid-1\n",
    "            return left\n",
    "\n",
    "        # dp+二分\n",
    "        envelopes.sort(key = lambda x:(x[0],-x[1]))\n",
    "        res = [envelopes[0][1]]\n",
    "        for i in range(1,len(envelopes)):\n",
    "            if envelopes[i][1]>res[-1]:\n",
    "                res.append(envelopes[i][1])\n",
    "            else:\n",
    "                ind=find(res,envelopes[i][1])\n",
    "                res[ind]=envelopes[i][1]\n",
    "        return len(res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        n = len(envelopes)\n",
    "        envelopes.sort(key= lambda x: (x[0], -x[1]))\n",
    "        dp = [envelopes[0][1]]\n",
    "        for i in range(1, n):\n",
    "            if (num := envelopes[i][1]) > dp[-1]:\n",
    "                dp.append(num)\n",
    "            else:\n",
    "                lo, hi = 0, len(dp)\n",
    "                while lo < hi:\n",
    "                    mid = (lo + hi) // 2\n",
    "                    if dp[mid] < num:\n",
    "                        lo = mid + 1\n",
    "                    else:\n",
    "                        hi = mid\n",
    "                # index = bisect.bisect_left(dp, num)\n",
    "                dp[lo] = num\n",
    "        return len(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:  \n",
    "       \n",
    "        envelopes = sorted(envelopes, key = lambda x: (x[0], - x[1]))\n",
    "        print(envelopes[0][1])\n",
    "\n",
    "        dp = [envelopes[0][1]]\n",
    "\n",
    "        for i in range(1, len(envelopes)):\n",
    "            if envelopes[i][1] >dp[-1]:\n",
    "                dp.append(envelopes[i][1])\n",
    "            else:\n",
    "                dp[bisect.bisect_left(dp, envelopes[i][1])] = envelopes[i][1]\n",
    "\n",
    "        return len(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, A: List[List[int]]) -> int:\n",
    "        # if not A:\n",
    "        #     return 0\n",
    "        A.sort(key = lambda x:(x[0], -x[1]))\n",
    "        arr = [A[0][1]]\n",
    "        for i in range(len(A)):\n",
    "            if A[i][1] > arr[-1]:\n",
    "                arr.append(A[i][1])\n",
    "            elif A[i][1] < arr[-1]:\n",
    "                # 1. 这里维护一个单调递增的arr，所以可以用二分法\n",
    "                # 2. 二分返回在arr中第一个比A[i][1]大的数\n",
    "                left, right =0, len(arr) - 1\n",
    "                while left < right:\n",
    "                    mid = (left + right) // 2 \n",
    "                    if arr[mid] >= A[i][1]:\n",
    "                        right = mid\n",
    "                    else:\n",
    "                        left = mid + 1 \n",
    "                arr[left] = A[i][1]\n",
    "        return len(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        # 解法1 dp 超时\n",
    "        n = len(envelopes)\n",
    "        # 按宽度进行升序排序 相同的按高度进行降序排序\n",
    "        envelopes.sort(key = lambda x: (x[0], -x[1]))\n",
    "\n",
    "        # 对高度数组寻找 LIS\n",
    "        # dp = [1] * n\n",
    "        # for i in range(n):\n",
    "        #     for j in range(i):\n",
    "        #         if envelopes[j][1] < envelopes[i][1]:\n",
    "        #             dp[i] = max(dp[i], dp[j]+1)\n",
    "        # return max(dp)\n",
    "\n",
    "        # 二分查找\n",
    "        top = [0] * n\n",
    "        piles = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            poker = envelopes[i][1]\n",
    "            \n",
    "            left, right = 0, piles\n",
    "            # 二分查找确定左边界\n",
    "            while left < right:\n",
    "                mid = (left + right) // 2\n",
    "                if top[mid] >= poker:\n",
    "                    right = mid \n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            \n",
    "            # 新建牌堆\n",
    "            if left == piles:\n",
    "                piles += 1\n",
    "            top[left] = poker \n",
    "            \n",
    "        return piles\n",
    "            \n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        if not envelopes:\n",
    "            return 0\n",
    "        envelopes.sort(key = lambda x : (x[0], -x[1]))\n",
    "        \"\"\"\n",
    "        dp = [1] * len(envelopes)\n",
    "        for i in range(1, len(envelopes)):\n",
    "            # x = 0\n",
    "            for j in range(i):\n",
    "                if envelopes[i][1] > envelopes[j][1]:\n",
    "                    # x = envelopes[j][1]\n",
    "                    dp[i] = max(dp[i], dp[j] + 1)\n",
    "        \"\"\"\n",
    "        f = [envelopes[0][1]]\n",
    "        for i in range(1, len(envelopes)):\n",
    "            if (num := envelopes[i][1]) > f[-1]:\n",
    "                f.append(num)\n",
    "            else:\n",
    "                index = bisect.bisect_left(f, num)\n",
    "                f[index] = num\n",
    "        return len(f)\n",
    "        # return max(dp)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        envelopes.sort(key=lambda x:(x[0],-x[1]))\n",
    "        length = len(envelopes)\n",
    "        res = [envelopes[0][1]]\n",
    "        for i in range(1, length):\n",
    "            if envelopes[i][1] > res[-1]:\n",
    "                res.append(envelopes[i][1])\n",
    "            else:\n",
    "                index = bisect_left(res, envelopes[i][1])\n",
    "                res[index] = envelopes[i][1]\n",
    "\n",
    "            # index = bisect_left(res, envelopes[i][1])\n",
    "            # if index < len(res):\n",
    "            #     res[index] = envelopes[i][1]\n",
    "            # else:\n",
    "            #     res.append(envelopes[i][1])\n",
    "        return len(res)\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        # 贪心 + 二分\n",
    "        envelopes.sort(key=lambda x: (x[0], -x[1]))\n",
    "        n = len(envelopes)\n",
    "\n",
    "        g = [envelopes[0][1]]\n",
    "        for i in range(1, n):\n",
    "            if envelopes[i][1] > g[-1]:\n",
    "                g.append(envelopes[i][1])\n",
    "            else:\n",
    "                j = bisect_left(g, envelopes[i][1])\n",
    "                g[j] = envelopes[i][1]\n",
    "        return len(g)\n",
    "\n",
    "        # 递推 O(n ** 2) TLE\n",
    "        # f[i] 表示以envelopes[i]为最外层信封时，可以套娃的信封个数\n",
    "        # envelopes.sort(key=lambda x: (x[0], -x[1]))\n",
    "        # n = len(envelopes)\n",
    "        # f = [0] * n\n",
    "\n",
    "        # for i in range(n):\n",
    "        #     for j in range(i):\n",
    "        #         if envelopes[j][1] < envelopes[i][1]:\n",
    "        #             f[i] = max(f[i], f[j])\n",
    "        #     f[i] += 1\n",
    "        # return max(f)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        envelopes.sort(key=lambda u: (u[0], -u[1]))\n",
    "        d = []\n",
    "        for w, h in envelopes:\n",
    "            if not d or h > d[-1]:\n",
    "                d.append(h)\n",
    "            else:\n",
    "                l, r = 0, len(d) - 1\n",
    "                loc = r\n",
    "                while l <= r:\n",
    "                    mid = (l + r) // 2\n",
    "                    if d[mid] >= h:\n",
    "                        loc = mid\n",
    "                        r = mid - 1\n",
    "                    else:\n",
    "                        l = mid + 1\n",
    "                d[loc] = h\n",
    "        return len(d)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        if not envelopes:\n",
    "            return 0\n",
    "        \n",
    "        n = len(envelopes)\n",
    "        envelopes.sort(key=lambda x: (x[0], -x[1]))\n",
    "\n",
    "        f=[envelopes[0][1]]\n",
    "        for i in range (1,n):\n",
    "            if envelopes[i][1]>f[-1]:\n",
    "                f.append(envelopes[i][1])\n",
    "            else:\n",
    "                index=bisect.bisect_left(f,envelopes[i][1])\n",
    "                f[index]=envelopes[i][1]\n",
    "        return len(f)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        envelopes = sorted(envelopes, key= lambda x:(x[0],-x[1]))\n",
    "        envelopes = [e[1] for e in envelopes]\n",
    "        up_sub = []\n",
    "        for e in envelopes:\n",
    "            l, r = 0, len(up_sub)-1\n",
    "            while l <= r:\n",
    "                m = (l+r)//2\n",
    "                if e>up_sub[m]:\n",
    "                    l = m+1\n",
    "                else:\n",
    "                    r = m-1\n",
    "            if l==len(up_sub):\n",
    "                up_sub.append(e)\n",
    "            else:\n",
    "                up_sub[l]=e\n",
    "        \n",
    "        return len(up_sub)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        # 需要满足两个条件的最长递增子序列, 长宽都要大于前一个信封的长宽才能被选择\n",
    "        if not envelopes:\n",
    "            return 0\n",
    "\n",
    "        n = len(envelopes)\n",
    "        envelopes.sort(key=lambda x:(x[0], -x[1]))\n",
    "        \n",
    "        # dp = [1] * n\n",
    "        # maxTmp = 1\n",
    "        # for i in range(1, n):\n",
    "        #     maxTmp = max(maxTmp, dp[i-1])\n",
    "        #     if maxTmp + 1 <= dp[i]:\n",
    "        #         continue\n",
    "        #     for j in range(i):\n",
    "        #         if envelopes[j][1] < envelopes[i][1]:\n",
    "        #             dp[i] = max(dp[i], dp[j] + 1)\n",
    "        # return max(dp)\n",
    "\n",
    "        LIS = [envelopes[0][1]]\n",
    "        for i in range(1,n):\n",
    "            pos = bisect.bisect_left(LIS, envelopes[i][1])\n",
    "            if pos == len(LIS):\n",
    "                LIS.append(envelopes[i][1])\n",
    "            else:\n",
    "                LIS[pos] = envelopes[i][1]\n",
    "        return len(LIS)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        envelopes = sorted(envelopes, key=lambda x: (x[0], -x[1]))\n",
    "        n = len(envelopes)\n",
    "\n",
    "        dp = []\n",
    "\n",
    "        for i in range(n):\n",
    "            j = bisect_left(dp, envelopes[i][1])\n",
    "            if j == len(dp):\n",
    "                dp.append(envelopes[i][1])\n",
    "            else:\n",
    "                dp[j] = envelopes[i][1]\n",
    "\n",
    "        return len(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, A: List[List[int]]) -> int:\n",
    "        if not A:\n",
    "            return 0\n",
    "        A.sort(key = lambda x:(x[0], -x[1]))\n",
    "        arr = [A[0][1]]\n",
    "        for i in range(len(A)):\n",
    "            if A[i][1] > arr[-1]:\n",
    "                arr.append(A[i][1])\n",
    "            elif A[i][1] < arr[-1]:\n",
    "                # 1. 这里维护一个单调递增的arr，所以可以用二分法\n",
    "                # 2. 二分返回在arr中第一个比A[i][1]大的数\n",
    "                left, right =0, len(arr) - 1\n",
    "                while left < right:\n",
    "                    mid = (left + right) // 2 \n",
    "                    if arr[mid] >= A[i][1]:\n",
    "                        right = mid\n",
    "                    else:\n",
    "                        left = mid + 1 \n",
    "                arr[left] = A[i][1]\n",
    "        return len(arr)\n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        envelopes = sorted(envelopes, key =lambda x:[x[1], -x[0]])\n",
    "        envelopes = [ x for x,y in envelopes]\n",
    "        def lower_bound(nums, target):\n",
    "            left = 0\n",
    "            right = len(nums)-1\n",
    "            while left <= right:\n",
    "                mid = (left + right) // 2\n",
    "                if nums[mid] < target:\n",
    "                    left = mid + 1\n",
    "                elif nums[mid] > target:\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            if left < 0 or left > len(nums)-1:\n",
    "                return -1\n",
    "            return left\n",
    "        piles = [envelopes[0]]\n",
    "        for i in range(1, len(envelopes)):\n",
    "            loc = lower_bound(piles, envelopes[i])\n",
    "            if loc == -1:\n",
    "                piles.append(envelopes[i])\n",
    "            else:\n",
    "                piles[loc] = envelopes[i]\n",
    "        return len(piles)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        if not envelopes: return 0\n",
    "        envelopes.sort(key = lambda x: (x[0], -x[1]))\n",
    "        n = len(envelopes)\n",
    "\n",
    "\n",
    "        # dp = [1] * n\n",
    "        # for i in range(n):\n",
    "        #     for j in range(i):\n",
    "        #         if envelopes[j][1] < envelopes[i][1]:\n",
    "        #             dp[i] = max(dp[j] + 1, dp[i])\n",
    "        \n",
    "        \n",
    "        # dp = [1 for i in range(len(envelopes))]\n",
    "        # envelopes = sorted(envelopes, key=lambda x:x[0]) \n",
    "        # for i in range(len(envelopes)):\n",
    "        #     for j in range(i):\n",
    "        #         if envelopes[i][0] > envelopes[j][0] and envelopes[i][1] > envelopes[j][1]:\n",
    "        #             if dp[i] < dp[j] + 1:\n",
    "        #                 dp[i] = dp[j] + 1\n",
    "        #return max(dp) \n",
    "\n",
    "        # 2 4 5 3 5\n",
    "        # 2 3 5 - -  \n",
    "        dp = [sys.maxsize] * n\n",
    "        for i in range(n):\n",
    "            idx = bisect.bisect_left(dp, envelopes[i][1]) \n",
    "            dp[idx] = envelopes[i][1]\n",
    "\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if dp[i] != sys.maxsize:\n",
    "                return i + 1 \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        envelopes.sort(key = lambda x: (x[0], -x[1]))\n",
    "        q = [(0, 0)]\n",
    "        \n",
    "        for _, h in envelopes:\n",
    "            l = 0\n",
    "            r = len(q) - 1\n",
    "            while l!=r:\n",
    "                m = l + r + 1>> 1\n",
    "                if q[m][0] < h:\n",
    "                    l = m\n",
    "                else:\n",
    "                    r = m - 1\n",
    "            dp = q[l][1] + 1\n",
    "            l += 1\n",
    "            while l < len(q):\n",
    "                if dp >= q[l][1]:\n",
    "                    del q[l]\n",
    "                else:\n",
    "                    break\n",
    "            q.insert(l, (h,dp))\n",
    "        return q[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        envelopes.sort(key=lambda x: (x[0], -x[1]))\n",
    "        tails, res = [float('inf')]*(len(envelopes)), 0\n",
    "        \n",
    "        for _, h in envelopes:\n",
    "            l, r = 0, res\n",
    "            while l < r:\n",
    "                mid = (l+r)//2\n",
    "                if tails[mid] < h:\n",
    "                    l = mid+1\n",
    "                else:\n",
    "                    r = mid\n",
    "            tails[l] = h\n",
    "            if l == res:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        # 降序保证在同宽里高是最大的, 先被选择,不会连续append, 但还是会被更新的\n",
    "        envelopes.sort(key = lambda x:(x[0],-x[1]))\n",
    "        print(envelopes)\n",
    "        nums = [e[1] for e in envelopes]\n",
    "\n",
    "        g = []\n",
    "        for x in nums:\n",
    "            i = bisect_left(g,x)\n",
    "            if i == len(g):\n",
    "                g.append(x) # 这在里更新长度 # 对应的优先排序x1更大的再签名，防止相同宽度的时候进行更新\n",
    "            else:\n",
    "                g[i] = x\n",
    "        return len(g)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        n = len(envelopes)\n",
    "        envelopes.sort(key = lambda x: (x[0], -x[1]))\n",
    "\n",
    "        res = [envelopes[0][1]]\n",
    "        for i in range(1,n):\n",
    "            num = envelopes[i][1]\n",
    "            if num>res[-1]:\n",
    "                res.append(num)\n",
    "            else:\n",
    "                idx = bisect_left(res, num)\n",
    "                res[idx] = num\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        if not envelopes:\n",
    "            return 0\n",
    "        envelopes.sort(key=lambda x: (x[0],-x[1]))\n",
    "        d = []\n",
    "        for w,h in envelopes:\n",
    "            if not d or h>d[-1]:\n",
    "                d.append(h)\n",
    "            else:\n",
    "                l,r= 0, len(d)-1\n",
    "                loc = r\n",
    "                while l<=r:\n",
    "                    mid = (r+l)//2\n",
    "                    if h<=d[mid]:\n",
    "                        loc = mid\n",
    "                        r = mid-1\n",
    "                    else:\n",
    "                        l = mid+1\n",
    "                d[loc] = h\n",
    "        return len(d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, A: List[List[int]]) -> int:\n",
    "        if not A:\n",
    "            return 0\n",
    "        A.sort(key = lambda x:(x[0], -x[1]))\n",
    "        arr = [A[0][1]]\n",
    "        for i in range(len(A)):\n",
    "            if A[i][1] > arr[-1]:\n",
    "                arr.append(A[i][1])\n",
    "            elif A[i][1] < arr[-1]:\n",
    "                # 1. 这里维护一个单调递增的arr，所以可以用二分法\n",
    "                # 2. 二分返回在arr中第一个比A[i][1]大的数\n",
    "                left, right =0, len(arr) - 1\n",
    "                while left < right:\n",
    "                    mid = (left + right) // 2 \n",
    "                    if arr[mid] >= A[i][1]:\n",
    "                        right = mid\n",
    "                    else:\n",
    "                        left = mid + 1 \n",
    "                arr[left] = A[i][1]\n",
    "        return len(arr)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        envelopes.sort(key = lambda x:(x[0], -x[1]))\n",
    "        envelopes = [e[1] for e in envelopes]\n",
    "        increase_ss = []\n",
    "        for e in envelopes:\n",
    "            l, r = 0, len(increase_ss)-1\n",
    "            while l<=r:\n",
    "                m = (l+r)//2\n",
    "                if e>increase_ss[m]:\n",
    "                    l=m+1\n",
    "                else:\n",
    "                    r=m-1\n",
    "            if l==len(increase_ss):\n",
    "                increase_ss.append(e)\n",
    "            else:\n",
    "                increase_ss[l]=e\n",
    "        return len(increase_ss)\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        envelopes.sort(key=lambda x: (x[0], -x[1]))\n",
    "        piles = 1\n",
    "        size = len(envelopes)\n",
    "        top = [sys.maxsize] * size\n",
    "        top[0] = envelopes[0][1]\n",
    "        for i in range(1, size):\n",
    "            left = 0\n",
    "            right = piles\n",
    "            while left <= right:\n",
    "                mid = int(left + (right - left) / 2)\n",
    "                if top[mid] < envelopes[i][1]:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            top[left] = envelopes[i][1]\n",
    "            if left >= piles:\n",
    "                piles += 1\n",
    "        return piles"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        envelopes.sort(key=lambda x:(x[0],-x[1]))\n",
    "        r=[x[1] for x in envelopes]\n",
    "        res=[]\n",
    "        for i in r:\n",
    "            if len(res)==0 or i > res[-1]:\n",
    "                res.append(i)\n",
    "            else:\n",
    "                res[bisect_left(res, i)] = i\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        \n",
    "        self.sorted_(envelopes)\n",
    "        print(envelopes)\n",
    "\n",
    "        lis_in2 = [i[1] for i in envelopes]\n",
    "        print(lis_in2)\n",
    "\n",
    "        return self.lengthOfLIS(lis_in2)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "    def sorted_(self, envs):\n",
    "        envs.sort()\n",
    "        # envs_r = copy.deepcopy(envs)\n",
    "        # envs_r.reverse()\n",
    "        lene = len(envs)\n",
    "\n",
    "        if lene == 1:\n",
    "            return None\n",
    "\n",
    "        st_rc = 0\n",
    "        st = 0\n",
    "\n",
    "        last_ = None\n",
    "\n",
    "        sorted_tmp = []\n",
    "\n",
    "        while st < lene:\n",
    "\n",
    "            # print(envs, sorted_tmp)\n",
    "\n",
    "            rst = lene - 1 - st\n",
    "            if envs[rst][0] == last_:\n",
    "                sorted_tmp.append(envs[rst])\n",
    "                # sorted_tmp.sort().reverse()\n",
    "            \n",
    "            else:\n",
    "                sti = 0\n",
    "                # print('st_rc', st_rc)\n",
    "                for i in range(rst + 1, st_rc + 1):\n",
    "                    # print(i, sti)\n",
    "                    envs[i] = sorted_tmp[sti]\n",
    "                    sti += 1\n",
    "\n",
    "\n",
    "                sorted_tmp = [envs[rst]]\n",
    "                st_rc = rst\n",
    "            \n",
    "            last_ = envs[rst][0]\n",
    "            \n",
    "            st += 1\n",
    "        \n",
    "        sti = 0\n",
    "        # print('st_rc', st_rc, rst)\n",
    "        for i in range(rst, st_rc + 1):\n",
    "            print(i, sti)\n",
    "            envs[i] = sorted_tmp[sti]\n",
    "            sti += 1\n",
    "                \n",
    "                \n",
    "            \n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "    # def sorted_(self, inlist):\n",
    "    #     leni = len(inlist)\n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "    \n",
    "\n",
    "    def lengthOfLIS(self, nums: List[int]) -> int:\n",
    "        # print(range(10 - 1, -1, -1))\n",
    "        # for i in range(9, -1, -1):\n",
    "        # print(i)\n",
    "\n",
    "        lenn = len(nums)\n",
    "\n",
    "        ssets = [[]]\n",
    "\n",
    "        for i in range(lenn):\n",
    "            if i == 0:\n",
    "                ssets[0].append(nums[i])\n",
    "            else:\n",
    "                self.searched(nums[i], ssets)\n",
    "\n",
    "        return len(ssets)\n",
    "\n",
    "    def searched(self, target, numlist):\n",
    "\n",
    "        left = 0\n",
    "        right = len(numlist)\n",
    "\n",
    "        if target > numlist[-1][-1]:\n",
    "            numlist.append([target])\n",
    "            return None\n",
    "\n",
    "        if target <= numlist[0][-1]:\n",
    "            numlist[0].append(target)\n",
    "            return None\n",
    "\n",
    "        # print(numlist)\n",
    "        while left < right:\n",
    "            mid = int(left + (right - left) / 2)\n",
    "\n",
    "            if numlist[mid][-1] == target:\n",
    "                numlist[mid].append(target)\n",
    "                return None\n",
    "\n",
    "            elif numlist[mid][-1] > target:\n",
    "                right = mid\n",
    "\n",
    "            elif numlist[mid][-1] < target:\n",
    "                left = mid\n",
    "\n",
    "            if left + 1 == right:\n",
    "                break\n",
    "\n",
    "        # print(left, numlist)\n",
    "        numlist[left + 1].append(target)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        300. 最长递增子序列 二维版\n",
    "        直接遍历 j 超时，需要优化：通过二分而不是线性遍历找到上一个元素\n",
    "        - 额外存一个有序数组，序列长度和最小值（最小值一定随着序列长度递增），那么就可以快速找到我们要的j\n",
    "        \"\"\"\n",
    "        envelopes.sort(key=lambda x:(x[0], -x[1]))\n",
    "        l = len(envelopes)\n",
    "        dp = [1 for _ in range(l+1)]\n",
    "        l_min_h = []\n",
    "        for i in range(l+1):\n",
    "            if i == 0:\n",
    "                dp[i] = 0\n",
    "                continue\n",
    "            if i == 1:\n",
    "                dp[i] = 1\n",
    "                l_min_h.append(envelopes[i-1][1])\n",
    "                continue\n",
    "            # for j in range(i):\n",
    "            #     envi = envelopes[i-1]\n",
    "            #     envj = envelopes[j-1]\n",
    "            #     if envi[0]>envj[0] and envi[1]>envj[1]:\n",
    "            #         dp[i] = max(dp[j]+1, dp[i])\n",
    "            envi = envelopes[i-1]\n",
    "            index = bisect.bisect_left(l_min_h, envi[1])\n",
    "            if index >= len(l_min_h):\n",
    "                l_min_h.append(envi[1])\n",
    "            else:\n",
    "                l_min_h[index] = envi[1]\n",
    "            dp[i] = dp[index]+1\n",
    "        return len(l_min_h)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        if not envelopes:\n",
    "            return 0\n",
    "        \n",
    "        n = len(envelopes)\n",
    "        envelopes.sort(key=lambda x: (x[0], -x[1]))\n",
    "\n",
    "        f = [envelopes[0][1]]\n",
    "        for i in range(1, n):\n",
    "            \n",
    "            if envelopes[i][1] > f[-1]:\n",
    "                f.append(envelopes[i][1])\n",
    "            else:\n",
    "                index = bisect.bisect_left(f, envelopes[i][1])\n",
    "                f[index] = envelopes[i][1]\n",
    "        \n",
    "        return len(f)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, a: List[List[int]]) -> int:\n",
    "        a.sort(key=lambda x:(x[0],-x[1]))\n",
    "        b=[c[1] for c in a]\n",
    "        dp=[]\n",
    "        for i,c in enumerate(b):\n",
    "            j=bisect_left(dp,c)\n",
    "            # 1 2 3 5\n",
    "            if j==len(dp): dp.append(c)\n",
    "            else:\n",
    "                dp[j]=c\n",
    "        return len(dp)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, a: List[List[int]]) -> int:\n",
    "        a.sort(key=lambda x:(x[0],-x[1]))\n",
    "        b=[c[1] for c in a]\n",
    "        dp=[]\n",
    "        for i,c in enumerate(b):\n",
    "            j=bisect_left(dp,c)\n",
    "            # 1 2 3 5\n",
    "            if j==len(dp): dp.append(c)\n",
    "            else:\n",
    "                dp[j]=c\n",
    "        return len(dp)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "#         if not envelopes:\n",
    "#             return 0\n",
    "#         N = len(envelopes)\n",
    "#         envelopes.sort()\n",
    "#         res = 0\n",
    "#         dp = [1] * N\n",
    "#         for i in range(N):\n",
    "#             for j in range(i):\n",
    "#                 if envelopes[j][0] < envelopes[i][0] and envelopes[j][1] < envelopes[i][1]:\n",
    "#                     dp[i] = max(dp[i], dp[j] + 1)\n",
    "#         return max(dp)        \n",
    "        \n",
    "        \n",
    "# class Solution:\n",
    "#     def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "#         if not envelopes:\n",
    "#             return 0\n",
    "#         N = len(envelopes)\n",
    "#         envelopes.sort(key=lambda x: (x[0], -x[1]))\n",
    "#         # envelopes.sort(key=lambda x: (x[0], x[1]))\n",
    "#         # print(envelopes)\n",
    "#         res = 0\n",
    "#         dp = [1] * N\n",
    "#         for i in range(N):\n",
    "#             for j in range(i):\n",
    "#                 if envelopes[j][1] < envelopes[i][1]:\n",
    "#                     dp[i] = max(dp[i], dp[j] + 1)\n",
    "#                     print(dp)\n",
    "#         return max(dp)\n",
    "    \n",
    "    \n",
    "    \n",
    "class Solution:\n",
    "    def maxEnvelopes(self, a: List[List[int]]) -> int:\n",
    "        a.sort(key=lambda x:(x[0],-x[1]))\n",
    "        b=[c[1] for c in a]\n",
    "        dp=[]\n",
    "        for i,c in enumerate(b):\n",
    "            j=bisect_left(dp,c)\n",
    "            # 1 2 3 5\n",
    "            if j==len(dp): dp.append(c)\n",
    "            else:\n",
    "                dp[j]=c\n",
    "        return len(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        def find(nums):\n",
    "            l = 0\n",
    "            r = lens - 1\n",
    "            ans = -1\n",
    "            while l <= r:\n",
    "                mid = (l+r) // 2\n",
    "                if nums <= ends[mid]:\n",
    "                    ans = mid\n",
    "                    r = mid - 1\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            return ans\n",
    "        envelopes.sort(key=lambda x:(x[0], -x[1]))\n",
    "        n = len(envelopes)\n",
    "        ends = [0 for _ in range(n)]\n",
    "        lens = 0\n",
    "        for i in range(n):\n",
    "            m = find(envelopes[i][1])\n",
    "            if m == -1:\n",
    "                ends[lens] = envelopes[i][1]\n",
    "                lens += 1\n",
    "            else:\n",
    "                ends[m] = envelopes[i][1]\n",
    "        return lens"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        def find(nums):\n",
    "            l = 0\n",
    "            r = lens - 1\n",
    "            ans = -1\n",
    "            while l <= r:\n",
    "                mid = (l+r) // 2\n",
    "                if nums <= ends[mid]:\n",
    "                    ans = mid\n",
    "                    r = mid - 1\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            return ans\n",
    "        envelopes.sort(key=lambda x:(x[0], -x[1]))\n",
    "        n = len(envelopes)\n",
    "        ends = [0 for _ in range(n)]\n",
    "        lens = 0\n",
    "        for i in range(n):\n",
    "            m = find(envelopes[i][1])\n",
    "            if m == -1:\n",
    "                ends[lens] = envelopes[i][1]\n",
    "                lens += 1\n",
    "            else:\n",
    "                ends[m] = envelopes[i][1]\n",
    "        return lens"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        # def lt354(envelopes):\n",
    "        #     envelopes.sort(key=lambda x:(x[0],x[1]))\n",
    "        #     n=len(envelopes)\n",
    "        #     dp=[1]*n\n",
    "        #     for i in range(1,n):\n",
    "        #         for j in range(i-1,-1,-1):\n",
    "        #             if envelopes[i][0]>envelopes[j][0] and envelopes[i][1]>envelopes[j][1]:\n",
    "        #                 dp[i]=max(dp[i],dp[j]+1)\n",
    "        #     print(dp)\n",
    "        #     return max(dp)\n",
    "        # return lt354(envelopes)\n",
    "\n",
    "        def lt354_2(envs):\n",
    "            envs.sort(key=lambda x:(x[0],-x[1]))\n",
    "            c=[e[1] for e in envs]\n",
    "            n=len(envs)\n",
    "            dp=[float('inf')]*n\n",
    "            for num in c:\n",
    "                idx=bisect.bisect_left(dp,num)\n",
    "                dp[idx]=num\n",
    "            for i in range(n-1,-1,-1):\n",
    "                if dp[i]!=float('inf'):return i+1\n",
    "        return lt354_2(envelopes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        # 一维升序，二维降序，求二维的最长递增子序列，真实天才\n",
    "        envelopes.sort(key = lambda x:(x[0],-x[1]))\n",
    "        nums = [i[1] for i in envelopes]\n",
    "        # 二分法求最长递增子序列\n",
    "        longst = []\n",
    "        for num in nums:\n",
    "            i = bisect_left(longst,num)\n",
    "            if i==len(longst):\n",
    "                longst.append(num)\n",
    "            else:\n",
    "                longst[i] = num\n",
    "        return len(longst)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        envelopes.sort(key=lambda x:(x[0], -x[1]))\n",
    "        height = [x[1] for _, x in enumerate(envelopes)]\n",
    "        return self.LIS(height)\n",
    "    \n",
    "    def LIS(self, nums):\n",
    "        tops = []\n",
    "        piles = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            l, r = 0, piles\n",
    "            while l < r:\n",
    "                mid = (l + r) // 2\n",
    "                if tops[mid] < num:\n",
    "                    l = mid + 1\n",
    "                else:\n",
    "                    r = mid\n",
    "            if l == piles:\n",
    "                piles += 1\n",
    "                tops.append(num)\n",
    "            else:\n",
    "                tops[l] = num\n",
    "        return piles"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        envelopes.sort(key=lambda x:(x[0],-x[1]))\n",
    "        b=[c[1] for c in envelopes]\n",
    "        dp=[]\n",
    "        for i,c in enumerate(b):\n",
    "            j=bisect_left(dp,c)\n",
    "            # 1 2 3 5\n",
    "            if j==len(dp): dp.append(c)\n",
    "            else:\n",
    "                dp[j]=c\n",
    "        return len(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def lengthOfLIS(self, nums: [int]) -> int:\n",
    "        tails, res = [0] * len(nums), 0\n",
    "        for num in nums:\n",
    "            i, j = 0, res\n",
    "            while i < j:\n",
    "                m = (i + j) // 2\n",
    "                if tails[m] < num: i = m + 1 # 如果要求非严格递增，将此行 '<' 改为 '<=' 即可。\n",
    "                else: j = m\n",
    "            tails[i] = num\n",
    "            if j == res: res += 1\n",
    "        return res\n",
    "\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        ## 先对envelope的第一个维度进行排序，随后计算第二个维度中的最长递增子序列\n",
    "        envelopes.sort(key = lambda x: (x[0],-x[1]))\n",
    "        nums = [envelope[1] for envelope in envelopes]\n",
    "        n = len(nums)\n",
    "        return self.lengthOfLIS(nums)    \n",
    "\n",
    "        # Dynamic programming + Dichotomy.\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, a: List[List[int]]) -> int:\n",
    "        a.sort(key=lambda x:(x[0],-x[1]))\n",
    "        b=[c[1] for c in a]\n",
    "        dp=[]\n",
    "        for i,c in enumerate(b):\n",
    "            j=bisect_left(dp,c)\n",
    "            # 1 2 3 5\n",
    "            if j==len(dp): dp.append(c)\n",
    "            else:\n",
    "                dp[j]=c\n",
    "        return len(dp)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, arr: List[List[int]]) -> int:\n",
    "        # sort increasing in first dimension and decreasing on second\n",
    "        arr.sort(key=lambda x: (x[0], -x[1]))\n",
    "\n",
    "        def lis(nums):\n",
    "            dp = []\n",
    "            for i in range(len(nums)):\n",
    "                idx = bisect_left(dp, nums[i])  #二分法\n",
    "                if idx == len(dp):\n",
    "                    dp.append(nums[i])  #append\n",
    "                else:\n",
    "                    dp[idx] = nums[i]  #replace\n",
    "            return len(dp)\n",
    "        # extract the second dimension and run the LIS\n",
    "        return lis([i[1] for i in arr])  #固定左侧，按右侧求LIS"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "#         if not envelopes:\n",
    "#             return 0\n",
    "#         N = len(envelopes)\n",
    "#         envelopes.sort()\n",
    "#         res = 0\n",
    "#         dp = [1] * N\n",
    "#         for i in range(N):\n",
    "#             for j in range(i):\n",
    "#                 if envelopes[j][0] < envelopes[i][0] and envelopes[j][1] < envelopes[i][1]:\n",
    "#                     dp[i] = max(dp[i], dp[j] + 1)\n",
    "#         return max(dp)        \n",
    "        \n",
    "        \n",
    "# class Solution:\n",
    "#     def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "#         if not envelopes:\n",
    "#             return 0\n",
    "#         N = len(envelopes)\n",
    "#         envelopes.sort(key=lambda x: (x[0], -x[1]))\n",
    "#         # envelopes.sort(key=lambda x: (x[0], x[1]))\n",
    "#         # print(envelopes)\n",
    "#         res = 0\n",
    "#         dp = [1] * N\n",
    "#         for i in range(N):\n",
    "#             for j in range(i):\n",
    "#                 if envelopes[j][1] < envelopes[i][1]:\n",
    "#                     dp[i] = max(dp[i], dp[j] + 1)\n",
    "#                     print(dp)\n",
    "#         return max(dp)\n",
    "    \n",
    "    \n",
    "    \n",
    "class Solution:\n",
    "    def maxEnvelopes(self, a: List[List[int]]) -> int:\n",
    "        a.sort(key=lambda x:(x[0],-x[1]))\n",
    "        b=[c[1] for c in a]\n",
    "        dp=[]\n",
    "        for i,c in enumerate(b):\n",
    "            j=bisect_left(dp,c)\n",
    "            # 1 2 3 5\n",
    "            if j==len(dp): dp.append(c)\n",
    "            else:\n",
    "                dp[j]=c\n",
    "        return len(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        envelopes.sort(key=lambda x:(x[0], -x[1]))\n",
    "        print(envelopes)\n",
    "        g = []\n",
    "\n",
    "        for w, h in envelopes:\n",
    "            p = bisect_left(g, h)\n",
    "            if p == len(g):\n",
    "                g.append(h)\n",
    "            else:\n",
    "                g[p] = h\n",
    "        return len(g)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        envelopes.sort(key = lambda k: [k[0], -k[1]])    \n",
    "        dp = []\n",
    "        for _, height in envelopes:\n",
    "            i = bisect.bisect_left(dp, height)            \n",
    "            if i < len(dp):\n",
    "                dp[i] = height\n",
    "            else:\n",
    "                dp.append(height)\n",
    "        return len(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        # 贪心 + 二分\n",
    "        envelopes.sort(key=lambda x: (x[0], -x[1]))\n",
    "        n = len(envelopes)\n",
    "\n",
    "        g = [envelopes[0][1]]\n",
    "        for i in range(1, n):\n",
    "            j = bisect_left(g, envelopes[i][1])\n",
    "            if envelopes[i][1] > g[-1]:\n",
    "                g.append(envelopes[i][1])\n",
    "            else:\n",
    "                j = bisect_left(g, envelopes[i][1])\n",
    "                g[j] = envelopes[i][1]\n",
    "        return len(g)\n",
    "\n",
    "        # 递推 O(n ** 2) TLE\n",
    "        # f[i] 表示以envelopes[i]为最外层信封时，可以套娃的信封个数\n",
    "        # envelopes.sort(key=lambda x: (x[0], -x[1]))\n",
    "        # n = len(envelopes)\n",
    "        # f = [0] * n\n",
    "\n",
    "        # for i in range(n):\n",
    "        #     for j in range(i):\n",
    "        #         if envelopes[j][1] < envelopes[i][1]:\n",
    "        #             f[i] = max(f[i], f[j])\n",
    "        #     f[i] += 1\n",
    "        # return max(f)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        envelopes.sort(key=lambda x:[x[0],-x[1]])\n",
    "  \n",
    "        b=[c[1] for c in envelopes]\n",
    "        #print(b)\n",
    "        dp=[]\n",
    "        for i,v in enumerate(b):\n",
    "            ind=bisect.bisect_left(dp,v)\n",
    "            \n",
    "            if ind==len(dp):\n",
    "                dp.append(v)\n",
    "            else:\n",
    "                dp[ind]=v\n",
    "            #print(dp)\n",
    "        #print(dp)\n",
    "        return len(dp)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        envelopes.sort(key=lambda x: (x[0], -x[1]))\n",
    "        dp = []\n",
    "        for _,height in envelopes:\n",
    "            left = bisect_left(dp, height)\n",
    "            if left == len(dp): dp.append(height)\n",
    "            else: dp[left] = height\n",
    "        return len(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        envelopes.sort(key=lambda x: (x[0], -x[1]))\n",
    "        dp = []\n",
    "        for _,height in envelopes:\n",
    "            left = bisect_left(dp, height)\n",
    "            if left == len(dp): dp.append(height)\n",
    "            else: dp[left] = height\n",
    "        return len(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        # envelopes = sorted(envelopes)\n",
    "        # n = len(envelopes)\n",
    "        # # @cache\n",
    "        # # def dfs(i):\n",
    "        # #     res = 0\n",
    "        # #     # cnt = 0\n",
    "        # #     for j in range(i):\n",
    "        # #         if envelopes[i][1] > envelopes[j][1] and envelopes[i][0] > envelopes[j][0]:\n",
    "        # #             res = max(res, dfs(j))\n",
    "        # #             # cnt = dfs(j)[1] + 1\n",
    "        # #     return res + 1\n",
    "        # # ans = 0\n",
    "        # # for i in range(n):\n",
    "        # #     res = dfs(i)\n",
    "        # #     if res > ans:\n",
    "        # #         ans = res\n",
    "        # # return ans\n",
    "        # f = [0] * n\n",
    "        # for i in range(n):\n",
    "        #     f[i] = 1\n",
    "        #     for j in range(i):\n",
    "        #         if envelopes[i][1] > envelopes[j][1] and envelopes[i][0] > envelopes[j][0]:\n",
    "        #             f[i] = max(f[j] + 1, f[i])\n",
    "        # ans = 0\n",
    "        # for i in range(n):\n",
    "        #     if f[i] > ans:\n",
    "        #         ans = f[i]\n",
    "        # return ans\n",
    "        if not envelopes:\n",
    "            return 0\n",
    "        n = len(envelopes)\n",
    "        envelopes.sort(key=lambda x: (x[0], -x[1]))\n",
    "\n",
    "        f = [envelopes[0][1]]\n",
    "        for i in range(1, n):\n",
    "            num = envelopes[i][1]\n",
    "            if num > f[-1]:\n",
    "                f.append(num)\n",
    "            else:\n",
    "                index = bisect_left(f, num)\n",
    "                f[index] = num\n",
    "        return len(f)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        envelopes.sort(key=lambda x: (x[0], -x[1]))\n",
    "        dp = []\n",
    "        for _,height in envelopes:\n",
    "            left = bisect_left(dp, height)\n",
    "            if left == len(dp): dp.append(height)\n",
    "            else: dp[left] = height\n",
    "        return len(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        n = len(envelopes)\n",
    "        envelopes.sort(key=lambda x: (x[0], -x[1]))\n",
    "        g = []\n",
    "        for _, x in envelopes:\n",
    "            j = bisect_left(g, x)\n",
    "            if j == len(g):\n",
    "                g.append(x)\n",
    "            else:\n",
    "                g[j] = x\n",
    "        return len(g)\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        envelopes.sort(key=lambda x: (x[0], -x[1]))\n",
    "        dp = []\n",
    "        for _,height in envelopes:\n",
    "            left = bisect_left(dp, height)\n",
    "            if left == len(dp):\n",
    "                dp.append(height)\n",
    "            else:\n",
    "                dp[left] = height\n",
    "        return len(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        envelopes.sort(key=lambda x: (x[0], -x[1]))\n",
    "        g = []\n",
    "        for _,x in envelopes:\n",
    "            j = bisect_left(g,x)\n",
    "            if j == len(g):\n",
    "                g.append(x)\n",
    "            else:\n",
    "                g[j] = x\n",
    "        return len(g)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        if not envelopes:\n",
    "            return 0\n",
    "        \n",
    "        n = len(envelopes)\n",
    "        envelopes.sort(key=lambda x: (x[0], -x[1]))\n",
    "\n",
    "        f = [envelopes[0][1]]\n",
    "        for i in range(1, n):\n",
    "            if (num := envelopes[i][1]) > f[-1]:\n",
    "                f.append(num)\n",
    "            else:\n",
    "                index = bisect.bisect_left(f, num)\n",
    "                f[index] = num\n",
    "        \n",
    "        return len(f)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        envelopes.sort(key=lambda x: (x[0], -x[1]))\n",
    "      \n",
    "        stack = []\n",
    "        for _, item in envelopes:\n",
    "            loc = bisect_left(stack, item)\n",
    "            if loc == len(stack):\n",
    "                stack.append(item)\n",
    "            else:\n",
    "                stack[loc] = item\n",
    "\n",
    "        return len(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        \n",
    "        if not envelopes:\n",
    "            return 0\n",
    "        envelopes.sort(key=lambda x:(x[0],-x[1]))\n",
    "        n=len(envelopes)\n",
    "        stack=[]\n",
    "        for i in range(n):\n",
    "            h=envelopes[i][1]            \n",
    "            if not stack or stack[-1]<h:\n",
    "                stack.append(h)\n",
    "            else:\n",
    "                index=bisect.bisect_left(stack,h)\n",
    "                stack[index]=h\n",
    "        return len(stack)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        envelopes.sort(key=lambda x: (x[0], -x[1]))\n",
    "        g = []\n",
    "        for _,x in envelopes:\n",
    "            j = bisect_left(g,x)\n",
    "            if j == len(g):\n",
    "                g.append(x)\n",
    "            else:\n",
    "                g[j] = x\n",
    "        return len(g)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        envelopes.sort(key=lambda x: (x[0], -x[1]))\n",
    "        g = []\n",
    "        for _,x in envelopes:\n",
    "            j = bisect_left(g,x)\n",
    "            if j == len(g):\n",
    "                g.append(x)\n",
    "            else:\n",
    "                g[j] = x\n",
    "        return len(g)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        import bisect\n",
    "        envelopes.sort(key = lambda x:(x[0],-x[1]))\n",
    "        \n",
    "        f = [envelopes[0][1]]\n",
    "        for i in range(1, len(envelopes)):\n",
    "            num = envelopes[i][1]\n",
    "            if num > f[-1]:\n",
    "                f.append(num)\n",
    "            else:\n",
    "                index = bisect.bisect_left(f, num)\n",
    "                f[index] = num\n",
    "        return len(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        envelopes.sort(key=lambda x: (x[0], -x[1]))\n",
    "        g = []\n",
    "        for _,x in envelopes:\n",
    "            j = bisect_left(g,x)\n",
    "            if j == len(g):\n",
    "                g.append(x)\n",
    "            else:\n",
    "                g[j] = x\n",
    "        return len(g)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        n = len(envelopes)\n",
    "        envelopes.sort(key=lambda x: (x[0],-x[1]))\n",
    "        hi = []\n",
    "        for wid, hei in envelopes:\n",
    "            hi.append(hei)\n",
    "        \n",
    "        def lis(hi) -> int:\n",
    "            res = 0\n",
    "            n = len(hi)\n",
    "            minends = [0 for i in range(n)] # [0, res)\n",
    "            for i, height in enumerate(hi):\n",
    "                idx = bisect_left(minends,height,0,res)\n",
    "                if idx == res:\n",
    "                    res += 1\n",
    "                minends[idx] = height\n",
    "            return res\n",
    "\n",
    "        return lis(hi) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        300. 最长递增子序列 二维版\n",
    "        直接遍历 j 超时，需要优化：通过二分而不是线性遍历找到上一个元素\n",
    "        - 对 h 排序是为了让 w 即使重复了，因为 h 下降，也不会构成序列，这样就不用考虑 w 了\n",
    "        - 额外存一个有序数组，序列长度和最小值（最小值一定随着序列长度递增），那么就可以快速找到我们要的j\n",
    "        \"\"\"\n",
    "        envelopes.sort(key=lambda x:(x[0], -x[1]))\n",
    "        l = len(envelopes)\n",
    "        l_min_h = []\n",
    "        for i in range(l+1):\n",
    "            envi = envelopes[i-1]\n",
    "            if i == 0:\n",
    "                continue\n",
    "            if i == 1:\n",
    "                l_min_h.append(envi[1])\n",
    "                continue\n",
    "\n",
    "            index = bisect.bisect_left(l_min_h, envi[1])\n",
    "            if index >= len(l_min_h):\n",
    "                l_min_h.append(envi[1])\n",
    "            else:\n",
    "                l_min_h[index] = envi[1]\n",
    "        return len(l_min_h)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        if len(envelopes) == 0:\n",
    "            return 0\n",
    "        n = len(envelopes)\n",
    "        envelopes.sort(key=lambda x:(x[0], -x[1]))\n",
    "\n",
    "        # -----\n",
    "        # dp = [1] * len(envelopes)\n",
    "        # for i in range(len(envelopes)):\n",
    "        #     for j in range(i):\n",
    "        #         if envelopes[j][1] < envelopes[i][1]:\n",
    "        #             dp[i] = max(dp[i], dp[j] + 1)\n",
    "        # return max(dp)\n",
    "        \n",
    "        f = [envelopes[0][1]]\n",
    "        for i in range(1, n):\n",
    "            if (envelopes[i][1] > f[-1]):\n",
    "                f.append(envelopes[i][-1])\n",
    "            else:\n",
    "                index = bisect.bisect_left(f, envelopes[i][1])\n",
    "                f[index] = envelopes[i][1]\n",
    "        return len(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    import bisect\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        envelopes.sort(key=lambda x:(x[0],-x[1]))\n",
    "\n",
    "        li=[]\n",
    "        for a,b in envelopes:\n",
    "            idx=bisect.bisect_left(li,b)\n",
    "            if idx==len(li):\n",
    "                li.append(b)\n",
    "            else:\n",
    "                li[idx]=b\n",
    "        return len(li)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        envelopes = sorted(envelopes, key=lambda x: (x[0], -x[1]))\n",
    "        stack = []\n",
    "        for w, h in envelopes: \n",
    "            if not stack:\n",
    "                stack.append(h)\n",
    "            else:\n",
    "                if h > stack[-1]:\n",
    "                    stack.append(h)\n",
    "                else:\n",
    "                    idx = self.bisect_left(stack, h)\n",
    "                    stack[idx] = h \n",
    "        \n",
    "        return len(stack)\n",
    "    \n",
    "    def bisect_left(self, arr, target) -> int: \n",
    "        left = 0 \n",
    "        right = len(arr) - 1 \n",
    "    \n",
    "        while left <= right:\n",
    "            mid = (left+right) // 2 \n",
    "            if arr[mid] == target:\n",
    "                right = mid - 1 \n",
    "            elif arr[mid] > target:\n",
    "                right = mid - 1 \n",
    "            elif arr[mid] < target:\n",
    "                left = mid + 1 \n",
    "        \n",
    "        return left \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        envelopes.sort(key=lambda x: (x[0], -x[1]))\n",
    "        g = []\n",
    "        for _,x in envelopes:\n",
    "            j = bisect_left(g,x)\n",
    "            if j == len(g):\n",
    "                g.append(x)\n",
    "            else:\n",
    "                g[j] = x\n",
    "        return len(g)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes) -> int:\n",
    "        envelopes.sort(key=lambda x: (x[0], -x[1]))\n",
    "        res = []\n",
    "        for e in envelopes:\n",
    "            right = e[1]\n",
    "            if len(res) == 0 or right > res[-1]:res.append(right)\n",
    "            else:\n",
    "                l, r = 0, len(res) - 1\n",
    "                while l < r:\n",
    "                    mid = l + r >> 1\n",
    "                    if res[mid] >= right:r = mid\n",
    "                    else:l = mid + 1\n",
    "                res[l] = min(res[l], right)\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        if not envelopes:\n",
    "            return 0\n",
    "        \n",
    "        n = len(envelopes)\n",
    "        envelopes.sort(key=lambda x: (x[0], -x[1]))\n",
    "\n",
    "        f = [envelopes[0][1]]\n",
    "        for i in range(1, n):\n",
    "            if (num := envelopes[i][1]) > f[-1]:\n",
    "                f.append(num)\n",
    "            else:\n",
    "                index = bisect.bisect_left(f, num)\n",
    "                f[index] = num\n",
    "        \n",
    "        return len(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelops: List[List[int]]) -> int:\n",
    "        envelops = sorted(envelops, key=lambda x: (x[0], -x[1]))\n",
    "        \n",
    "        n = len(envelops)\n",
    "        \n",
    "        dp = [[0, 0] for _ in range(n)]\n",
    "        dp[0] = envelops[0]\n",
    "        \n",
    "        j = 0\n",
    "        for i in range(n):\n",
    "            w, h = envelops[i]\n",
    "            \n",
    "            if w > dp[j][0] and h > dp[j][1]:\n",
    "                j += 1\n",
    "                dp[j][0], dp[j][1] = w, h\n",
    "            else:\n",
    "                left = 0\n",
    "                right = j\n",
    "                \n",
    "                while left < right:\n",
    "                    mid = left + (right - left) // 2\n",
    "                    \n",
    "                    if dp[mid][0] < envelops[i][0] and dp[mid][1] < envelops[i][1]:\n",
    "                        left = mid + 1\n",
    "                    else:\n",
    "                        right = mid\n",
    "                \n",
    "                dp[left][0], dp[left][1] = w, h\n",
    "        \n",
    "        return j + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "\n",
    "\n",
    "        n = len(envelopes)\n",
    "        envelopes.sort(key=lambda x: (x[0], -x[1]))\n",
    "\n",
    "        f = [envelopes[0][1]]\n",
    "        for i in range(1, n):\n",
    "            if (num := envelopes[i][1]) > f[-1]:\n",
    "                f.append(num)\n",
    "            else:\n",
    "                index = bisect.bisect_left(f, num)\n",
    "                f[index] = num\n",
    "        \n",
    "        return len(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        envelopes.sort(key = lambda x:x[1], reverse=True)\n",
    "        envelopes.sort(key = lambda x:x[0], reverse=False)\n",
    "        res = 0\n",
    "        top = [0] * len(envelopes)\n",
    "        for i in range(len(envelopes)):\n",
    "            num = envelopes[i][1]\n",
    "            left, right = 0, res\n",
    "            while left < right:\n",
    "                mid = (left+right)//2\n",
    "                if top[mid] > num:\n",
    "                    right = mid\n",
    "                elif top[mid] < num:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid\n",
    "                \n",
    "            if left == res:\n",
    "                res += 1\n",
    "            top[left] = num\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        if not envelopes:\n",
    "            return 0\n",
    "        \n",
    "        n = len(envelopes)\n",
    "        envelopes.sort(key=lambda x: (x[0], -x[1]))\n",
    "\n",
    "        f = [envelopes[0][1]]\n",
    "        for i in range(1, n):\n",
    "            if (num := envelopes[i][1]) > f[-1]:\n",
    "                f.append(num)\n",
    "            else:\n",
    "                index = bisect.bisect_left(f, num)\n",
    "                f[index] = num\n",
    "        \n",
    "        return len(f)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n",
    "        if not envelopes:\n",
    "            return 0\n",
    "        n=len(envelopes)\n",
    "        envelopes.sort(key=lambda x:(x[0],-x[1]))\n",
    "        g = []\n",
    "        for i, x in envelopes:\n",
    "            idx = bisect_left(g, x)\n",
    "            if idx == len(g):\n",
    "                g.append(x)\n",
    "            else:\n",
    "                g[idx] = x\n",
    "        return len(g)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
